;;; Homework of SICP
;;; Chapter 1
(define (square x)
  (* x x))
(define (fast-expt b n)
  (cond ((= n 0) 1)
        ((even? n) (fast-expt (square b) (/ n 2)))
        (else (* b (fast-expt b (- n 1))))))
(define (iter-expt a b n)
  (cond ((= n 0) a)
        ((even? n) (iter-expt a (square b) (/ n 2)))
        (else (iter-expt (* a b) b (- n 1)))))
(define (fast-expt-1 b n)
  (iter-expt 1 b n))
(define (smallest-divisor n)
  (find-divisor n 2))
(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))
(define (divides? a b)
  (= (remainder b a) 0))
(define (prime? n)
  (= (smallest-divisor n) n))
(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? m)
         (remainder (square (expmod base (/ exp 2) m)) m))
        (else (remainder (* base (expmod base (- exp 1) m)) m))))
(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1)))))
(define (fast-prime? n times)
  (cond ((= times 0) #t)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else #f)))
(define (miller-rabin-test n)
  (define (try-it a)
    (= (expmod-1 a (- n 1) n) 1))
  (try-it (+ 1 (random (- n 1)))))
(define (expmod-1 base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (square-mod-test (expmod-1 base (/ exp 2) m) m))
        (else (remainder (* base (expmod-1 base (- exp 1) m)) m))))
(define (square-mod-test test-remainder m)
  (cond ((or (= test-remainder 1)
             (= test-remainder (- m 1)))
         (remainder (square test-remainder) m))
        (else (cond ((= (remainder (square test-remainder) m) 1)
                     0)
                    (else
                     (remainder (square test-remainder) m))))))
(define tolerance 0.00001)
(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (display next)
      (newline)
      (if (close-enough? next guess)
          next
          (try next))))
  (try first-guess))
(define (cont-frac n d k)
  (cond ((= k 1) (/ (n k) (d k)))
        (/ (n (- k 1)) (+ (d (- k 1))
                          (cont-frac n d (- k 1))))))
;;;Chapter 2
(define (filter predicate sequence)
  (cond ((null? sequence) '())
        ((predicate (car sequence))
         (cons (car sequence)
               (filter predicate (cdr sequence))))
        (else (filter predicate (cdr sequence)))))
(define (accumulate op initial sequence)
  (cond ((null? sequence) initial)
        (else (op (car sequence)
                  (accumulate op initial (cdr sequence))))))
(define (enumerate-interval low high)
  (cond ((> low high) '())
        (else (cons low (enumerate-interval (+ low 1) high)))))
(define (enumerate-tree tree)
  (cond ((null? tree) '())
        ((not (pair? tree)) (list tree))
        (else (append (enumerate-tree (car tree))
                      (enumerate-tree (cdr tree))))))
(define (fold-left op initial sequence)
  (define (iter result rest)
    (cond ((null? rest) result)
          (else (iter (op result (car rest)) (cdr rest)))))
  (iter initial sequence))
(define (reverse sequence)
  (accumulate (lambda (x y)
                (append y (list x))) '() sequence))
(define (reverse sequence)
  (fold-left (lambda (x y)
               (cons y x)) '() sequence))
(define (enumerate-split n)
  (map (lambda (x)
         (cond ((> (- n x) 0)
                (list x (- n x))))) (enumerate-interval 1 (- n 1))))
(define (enumerate-three n)
  (accumulate (lambda (x result)
                (append (map (lambda (z)
                               (cons x z))
                             (filter (lambda (y)
                                       (and (not (= x (car y)))
                                            (not (= x (cadr y)))
                                            (not (= (car y) (cadr y)))))
                                     (enumerate-split (- n x))))
                        result))
              '() (enumerate-interval 1 (- n 1))))
(define (flatmap proc seq)
  (accumulate append '() (map proc seq)))
